package me.algo.tree;

import java.util.LinkedList;
import java.util.Objects;

/**
 * @author guozheng
 * @date 2024/4/18
 */
public class T4 {
    public static void main(String[] args) {

    }

    /**
     * 112. 路径总和
     * @param root
     * @param targetSum
     * @return
     */
    static public boolean hasPathSum(TreeNode root, int targetSum) {
        if (Objects.isNull(root)) {
            return false;
        }
        Pair pair = new Pair(root, 0);
        LinkedList<Pair> queue = new LinkedList<>();
        queue.addLast(pair);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                size--;
                Pair p = queue.removeFirst();
                TreeNode node = p.node;
                if (Objects.isNull(node.left) && Objects.isNull(node.right)) {
                    // 叶子节点
                    int val = node.val + p.sum;
                    if (val == targetSum) {
                        return true;
                    }
                }
                if (Objects.nonNull(node.left)) {
                    Pair lp = new Pair(node.left, node.val + p.sum);
                    queue.addLast(lp);
                }
                if (Objects.nonNull(node.right)) {
                    Pair rp = new Pair(node.right, node.val + p.sum);
                    queue.addLast(rp);
                }
            }
        }
        return false;
    }


    static record Pair(TreeNode node, int sum) {
    }
}
